package cn.yuemouren.dynamicprogramming;

import java.util.Arrays;

/**
 * <p>
 * 凑零钱问题
 * </p>
 *
 * @author Timi
 * @date 2021/5/14 下午3:07
 **/
public class CollectChange {

    /**
     * 凑钱的最小数量
     *
     * @param coins  钱的池子
     * @param amount 钱数
     *
     * @return
     */
    public int coinChange1(int[] coins, int amount) {
        //结束条件
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        Integer minValue = Integer.MAX_VALUE;
        for (int item : coins) {
            Integer min = coinChange1(coins, amount - item);
            if (min == -1) {
                continue;
            }
            minValue = Math.min(minValue, min + 1);
        }
        return minValue != Integer.MAX_VALUE ? minValue : -1;
    }

    /**
     * 凑钱的最小数量(带备忘录)
     *
     * @param coins  钱的池子
     * @param amount 钱数
     *
     * @return
     */
    public int coinChange2(int[] coins, int amount) {
        int[] cache = new int[amount + 1];
        return coin(coins, amount, cache);
    }

    public int coin(int[] coins, int amount, int[] cache) {
        int i = cache[amount];
        if (i > 0) {
            return i;
        }
        //结束条件
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        Integer minValue = Integer.MAX_VALUE;
        for (int item : coins) {
            Integer min = coin(coins, amount - item, cache);
            if (min == -1) {
                continue;
            }
            minValue = Math.min(minValue, min + 1);
        }
        cache[amount] = minValue != Integer.MAX_VALUE ? minValue : -1;
        return cache[amount];
    }

    /**
     * 凑钱的最小数量(迭代)
     *
     * @param coins  钱的池子
     * @param amount 钱数
     *
     * @return
     */
    public int coinChange3(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        //初始化所有数据
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
               if(i - coin < 0) {
                   continue;
               }
               dp[i] = Math.min(dp[i],dp[i - coin] + 1);
            }
        }
        return (dp[amount] > amount) ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] items = {1, 2, 5};
        CollectChange cc = new CollectChange();
        Integer num = cc.coinChange3(items, 11);
        System.out.println(num);
    }
}
